package com.laotang.第_4_章_哈希表.力扣_380_O1时间插入删除和获取随机元素;

import java.util.*;

/**
 * @官方网站 : https://douma.ke.qq.com
 * @微信公众号 : 抖码课堂
 * @官方微信号 : bigdatatang01
 * 抖码算法，让算法学习变的简单有趣
 * @作者 : 老汤
 */
public class _380_insert_delete_getrandom_o1 {
    /* 380. O(1) 时间插入、删除和获取随机元素
    设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
        insert(val)：当元素 val 不存在时，向集合中插入该项。
        remove(val)：元素 val 存在时，从集合中移除该项。
        getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

     // 初始化一个空的集合。
    RandomizedSet randomSet = new RandomizedSet();

    // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
    randomSet.insert(1);

    // 返回 false ，表示集合中不存在 2 。
    randomSet.remove(2);

    // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
    randomSet.insert(2);

    // getRandom 应随机返回 1 或 2 。
    randomSet.getRandom();

    // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
    randomSet.remove(1);

    // 2 已在集合中，所以返回 false 。
    randomSet.insert(2);

    // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
    randomSet.getRandom();
     */
}

class RandomizedSet {
    private Map<Integer, Integer> idxMap;
    private List<Integer> nums;
    private Random rand = new Random();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        this.nums = new ArrayList<>();
        this.idxMap = new HashMap<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (idxMap.containsKey(val)) return false;
        idxMap.put(val, nums.size());
        nums.add(val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!idxMap.containsKey(val)) return false;

        // 拿到需要删除的元素在列表中的索引位置
        int index = idxMap.get(val);

        // 将列表中的最后一个元素覆盖掉需要删除的元素
        int lastNum = nums.get(nums.size() - 1);
        nums.set(index, lastNum);

        // 更新最后一个元素的索引
        idxMap.put(lastNum, index);

        // 删除数组列表中的最后一个元素
        nums.remove(nums.size() - 1);
        // 从 map 中删除指定的元素
        idxMap.remove(val);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }
}
